package com.yeung.swordoffer;

public class 二维数组查找 {
    public static void main(String[] args) {

    }

    /**
     * 利用二维数组由上到下，由左到右递增的规律，
     * 那么选取右上角或者左下角的元素a[row][col]与target进行比较，
     * 当target小于元素a[row][col]时，那么target必定在元素a所在行的左边,
     * 即col--；
     * 当target大于元素a[row][col]时，那么target必定在元素a所在列的下边,
     * 即row++；
     *
     * @param target
     * @param array
     * @return
     */
    public boolean Find(int target, int[][] array) {
        int rows = array.length;
        int cols = array[0].length;
        int row = rows - 1, col = 0;//从左下角开始找
        while (row >= 0 && col < cols) {
            if (target < array[row][col]) {
                row--;
            } else if (target > array[row][col]) {
                col++;
            } else {
                return true;
            }
        }
        //查找越界, 返回false, 没找到
        return false;
    }
}
